Old English oþer "the second" (adj.), also as a pronoun, "one of the two, other," from Proto-Germanic *antharaz (cf. Old Saxon athar, Old Frisian other, Old Norse annarr, Middle Dutch and Dutch ander, Old High German andar, German ander, Gothic anþar "other").
These are from PIE *an-tero-, variant of *al-tero- "the other of two" (cf. Lithuanian antras, Sanskrit antarah "other, foreign," Latin alter), from root *al- "beyond" (see alias) + adjectival comparative suffix *-tero-. The Old English, Old Saxon, and Old Frisian forms show "a normal loss of n before fricatives" [Barnhart]. Meaning "different" is mid-13c.
Sense of "second" was detached from this word in English (which uses second, from Latin) and German (zweiter, from zwei "two") to avoid ambiguity. In Scandinavian, however, the second floor is still the "other" floor (e.g. Swedish andra, Danish anden). Also cf. Old English oþergeara "next year."
The other woman "a woman with whom a man begins a love affair while he is already committed" is from 1855. The other day originally (mid-12c.) was "the next day;" later (c.1300) "yesterday;" and now, loosely, "a day or two ago" (early 15c.). Phrase other half in reference to either the poor or the rich, is recorded from c.1600.
La moitié du monde ne sçayt comment l'aultre vit. [Rabelais, "Pantagruel," 1532]
early 13c., contraction of Old English æfre ælc "each of a group," literally "ever each" (Chaucer's everich), from each with ever added for emphasis, as the word is still felt to need emphasis (e.g. Modern English every last ..., every single ..., etc.).
Cf. everybody, everything, etc. The word everywhen is attested from 1843 but never caught on; neither did everyhow (1837). Slang phrase every Tom, Dick, and Harry dates from at least 1734, from common English given names.